package ifmo.compiler.task21.parser;

import java.util.ArrayList;
import java.util.HashSet;

import ifmo.compiler.task21.parser.symbols.EndSymbol;
import ifmo.compiler.task21.parser.symbols.Epsilon;
import ifmo.compiler.task21.parser.symbols.Nonterminal;
import ifmo.compiler.task21.parser.symbols.Symbol;
import ifmo.compiler.task21.parser.symbols.Terminal;
import ifmo.compiler.task21.parser.symbols.SymbolType;

public class PredictiveAnalysTableCreater {
	private SpecialGrammarFunction _first;
	private SpecialGrammarFunction _follow;
	private Production[] _grammar;
	private Terminal[] _terminals;
	private Nonterminal[] _nonterminals;

	public PredictiveAnalysTableCreater() {
		_first = new SpecialGrammarFunction();
		_follow = new SpecialGrammarFunction();
	}

	private void calcFirstFunction() {
		boolean bWasChange = true;
		Epsilon epsilon = new Epsilon();

		_first.clear();

		for (Terminal t : _terminals) {
			_first.insert(t, t);
		}
		_first.insert(epsilon, epsilon);

		while (bWasChange) {
			bWasChange = false;

			for (Production prod : _grammar) {
				Symbol head = prod.getHead();
				Symbol[] tail = prod.getTail();

				// 1. Production X -> epsilon
				if (tail.length == 1 && tail[0].getType() == SymbolType.Epsilon
						&& !_first.contains(head, epsilon)) {
					_first.insert(head, new Epsilon());
					bWasChange = true;
				}

				// 2. Production X -> Y1Y2..Y3
				boolean bContainEpsilon = true;
				for (Symbol y : tail) {
					HashSet<Symbol> set = _first.getValues(y);

					for (Symbol a : set) {
						if (a.getType() == SymbolType.Terminal && !_first.contains(head, a)) {
							_first.insert(head, a);
							bWasChange = true;
						}
					}

					if (!set.contains(new Epsilon())) {
						bContainEpsilon = false;
						break;
					}
				}

				if (bContainEpsilon && !_first.contains(head, epsilon)) {
					_first.insert(head, epsilon);
					bWasChange = true;
				}
			}
		}
	}

	private HashSet<Symbol> calcFirstFunction(ArrayList<Symbol> symbs) {
		HashSet<Symbol> result = new HashSet<Symbol>();

		boolean bContainEpsilon = true;
		for (Symbol y : symbs) {
			HashSet<Symbol> set = _first.getValues(y);

			for (Symbol a : set) {
				if (a.getType() == SymbolType.Terminal) {
					result.add(a);
				}
			}

			if (!set.contains(new Epsilon())) {
				bContainEpsilon = false;
				break;
			}
		}

		if (bContainEpsilon) {
			result.add(new Epsilon());
		}

		return result;
	}

	private void calcFollowFunction()
	{
		// 1. $ in Follow(S), s - start symbol
		for (Nonterminal X : _nonterminals)
		{
			if (X.IsStartSymbol())
			{
				_follow.insert(X, new EndSymbol());
				break;
			}
		}
		
		boolean bWasChange = true;
		while (bWasChange)
		{
			bWasChange = false;
			
			for (Production prod : _grammar)
			{
				Symbol head = prod.getHead();
				Symbol[] tail = prod.getTail();
				
				// 1-2. A->{alpha}{B}{beta}
				if (tail.length > 1)
				{
					ArrayList<Symbol> beta = new ArrayList<Symbol>();
					
					for (int i = 1; i < tail.length; i++)
					{
						beta.add(tail[i]);
					}
					
					for (int i = 1; i < tail.length; i++)
					{
						Symbol B = tail[i-1];
						if (B.getType() == SymbolType.Nonterminal)
						{
							// 1. A->{alpha}{B}{beta} : all from FIRST(beta) -> FOLLOW (B)
							HashSet<Symbol> betaFirst = calcFirstFunction(beta);
							
							for (Symbol x : betaFirst)
							{
								if ((x.getType() != SymbolType.Epsilon) && !_follow.contains(B, x))
								{
									_follow.insert(B, x);
									bWasChange = true;
								}
							}
							
							// 2.  A->{alpha}{B}{beta} : if epsilon in FIRST({beta})
							// then all from FOLLOW(A) -> FOLLOW(B)
							if (betaFirst.contains(new Epsilon()))
							{
								HashSet<Symbol> followA = _follow.getValues(head);
								
								for (Symbol x : followA)
								{
									if (!_follow.contains(B, x))
									{
										_follow.insert(B, x);
										bWasChange = true;
									}
								}
							}
						}	
						beta.remove(0);
					}
				}
				
				// 2.  A->{alpha}{B} then all from FOLLOW(A) -> FOLLOW(B)
				{
					Symbol B = tail[tail.length-1];
					HashSet<Symbol> followA = _follow.getValues(head);
					
					for (Symbol x : followA)
					{
						if (!_follow.contains(B, x) && B.getType() == SymbolType.Nonterminal)
						{
							_follow.insert(B, x);
							bWasChange = true;
						}
					}
				}
			}
		}
	}

	public PredictiveAnalysTable create(Production[] grammar,
			Terminal[] terminals, Nonterminal[] nonterminals) throws Exception {
		PredictiveAnalysTable table = new PredictiveAnalysTable();
		
		_grammar = grammar;
		_terminals = terminals;
		_nonterminals = nonterminals;
		
		calcFirstFunction();
		calcFollowFunction();
		
		for (Production prod : _grammar)
		{
			Symbol head = prod.getHead();
			Symbol[] tail = prod.getTail();
			
			// A -> {alpha}
			// 1. For all terminals a from  FIRST({alpha}) insert
			// A -> {alpha} to M[A, a]
			ArrayList<Symbol> tailList = new ArrayList<Symbol>();
			for (Symbol x : tail) tailList.add(x);
			HashSet<Symbol> firstAlpha = calcFirstFunction(tailList);
			for (Symbol a : firstAlpha)
			{
				if (a.getType() == SymbolType.Terminal)
				{
					table.InsertProduction((Nonterminal)head, a, prod);
				}
			}
			
			// 2. Epsilon in FIRST(alpha) then for all terminals b from
			// FOLLOW(A) insert A->{alpha} to M[A,b]
			// And if $ in FOLLOW(A), then insert A->{alpha} to M[A, $]
			if (firstAlpha.contains(new Epsilon()))
			{
				HashSet<Symbol> followA = _follow.getValues(head);
				
				for (Symbol b : followA)
				{
					if (b.getType() == SymbolType.Terminal)
					{
						table.InsertProduction((Nonterminal)head, b, prod);
					}
				}
				
				if (followA.contains(new EndSymbol()))
				{
					table.InsertProduction((Nonterminal)head, new EndSymbol(), prod);
				}
			}
		}
		
		return table;
	}
}
